package SchoolGames;

import java.util.Arrays;

public class Main {
    public static void insertSort(int[] arr) {
        int bound = 1;
        for (; bound < arr.length; bound++) {
            int index = bound - 1;
            int v = arr[bound];
            for (; index >= 0; index--) {
                if (arr[index] > v) {
                    arr[index + 1] = arr[index];
                }else {
                    break;
                }
            }
            arr[index + 1] = v;
        }
    }

    public static void shellSort(int[] arr) {
        int gap = arr.length / 2;
        for (; gap >= 1;gap /= 2) {
            _shell(arr, gap);
        }
    }

    private static void _shell(int[] arr, int gap) {
        int bound = gap;
        for (; bound < arr.length; bound++) {
            int index = bound - gap;
            int v = arr[bound];
            for (; index >= 0; index -= gap) {
                if (arr[index] > v) {
                    arr[index + gap] = arr[index];
                }else {
                    break;
                }
            }
            arr[index + gap] = v;
        }
    }

    // 选择排序
    public static void selectSort(int[] arr) {
        int bound = 0;
        for (; bound < arr.length; bound++) {
            for (int cur = bound + 1; cur < arr.length; cur++) {
                if (arr[bound] > arr[cur]) {
                    swap(arr, bound, cur);
                }
            }
        }
    }

    private static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

    // 堆排序
    public static void heapSort(int[] arr) {
        createHeap(arr);
        int size = arr.length;
        for (int index = arr.length - 1; index >= 0; index--) {
            swap(arr, 0, index);
            size--;
            shiftDown(arr, size, 0);
        }
    }

    private static void createHeap(int[] arr) {
        int index = (arr.length - 1 - 1) / 2;
        for (; index >= 0; index--) {
            shiftDown(arr, arr.length, index);
        }
    }

    private static void shiftDown(int[] arr, int size, int index) {
        int parent = index;
        int child = 2 * parent + 1;
        while (child < size) {
            if (child + 1 < size && arr[child + 1] > arr[child]) {
                child = child + 1;
            }
            if (arr[child] > arr[parent]) {
                swap(arr, child, parent);
            }else {
                break;
            }
            parent = child;
            child = 2 * child + 1;
        }
    }

    public static void bubbleSort(int[] arr) {
        int bound = 0;
        for (; bound < arr.length; bound++) {
            for (int index = arr.length - 1; index - 1 >= bound; index--) {
                if (arr[index] < arr[index - 1]) {
                    swap(arr, index, index - 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr ={9,5,2,7,6,4,8,9};
//        insertSort(arr);
//        shellSort(arr);
//        selectSort(arr);
//        heapSort(arr);
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
